# -*- coding: utf-8 -*-

"""
@Time    : 2020/2/20 9:16
@Author  : Chen Liu
@FileName: danci_jielong.py
@Software: PyCharm

"""


# 错误解法：粗暴遍历，遗漏了包含在字典中的单词，死循环
# class Solution:
#     def ladderLength(self, beginWord: str, endWord: str, wordList: [str]) -> int:
#         count = 0
#         length = len(beginWord)
#         flag = [0 if beginWord[i] == endWord[i] else 1 for i in range(length)]
#         while beginWord != endWord:
#             print("beginWord: ", beginWord)
#             for i in range(length):
#                 if beginWord[i] == endWord[i]:
#                     continue
#                 else:
#                     j = i
#                     while j < length:
#                         tmp =beginWord
#                         beginWord = beginWord[:j] + endWord[j] + beginWord[j+1:]
#                         print("new-str: ", beginWord)
#                         if flag[j] and beginWord in wordList:
#                             count += 1
#                             break
#                         else:
#                             j += 1
#                             beginWord = tmp
#
#                 break
#         return count


# 解法二：广度优先搜索
# import collections
# class Solution:
#     def ladderLength(self, beginWord: str, endWord: str, wordList: [str]) -> int:
#         if endWord not in wordList or not beginWord or not endWord or not wordList:
#             return 0
#         L = len(beginWord)
#         # 定义dic, 用于存储key值相同的word,每次都遮盖其中的一位，保留遮盖后相同的元素
#         dic = collections.defaultdict(list)
#         for w in wordList:
#             for i in range(L):
#                 key = w[0:i] + '*' + w[i + 1:]
#                 dic[key].append(w)
#         print("dic: ", dic)
#
#         # 进行深度优先搜索
#         queue = [(beginWord, 1)]
#         # 存储已经访问过的单词
#         visited = {beginWord: True}
#         while queue:
#             # 针对每个单词, 均进行判断.
#             # pop(0)返回左侧第一个元素
#             cur, level = queue.pop(0)
#             print("cur: ", cur)
#             for i in range(L):
#                 key = cur[0:i] + '*' + cur[i + 1:]
#                 print("key: ", key)
#                 for w in dic[key]:
#                     # 找到
#                     if w == endWord:
#                         return level + 1
#                     # 将未判断的单词, 写入queue中
#                     if w not in visited:
#                         visited[w] = True
#                         queue.append((w, level + 1))
#                         print("queue: ", queue)
#                 # 说明key对应的单词, 均已经判断完毕
#                 dic[key] = []
#         return 0


# 解法二：宽度优先遍历 预先考虑每一层所有的可能性（层次遍历）
# class Solution:
#     def ladderLength(self, beginWord: str, endWord: str, wordList: [str]) -> int:
#         if endWord not in wordList or beginWord == endWord:
#             return 0
#
#         letter = 'abcdefghijklmnopqrstuvwxyz'
#         visit = set()
#         wordList = set(wordList)
#         from collections import deque
#         q = deque()
#         q.append([beginWord, 0])
#
#         while q:
#            cur, count = q.popleft()
#             if cur == endWord:
#                 return count + 1
#             for i in range(len(cur)):
#                 for j in range(26):
#                     word = cur[:i] + letter[j] + cur[i + 1:]
#                     if word in wordList and word not in visit:
#                         visit.add(word)
#                         q.append([word, count + 1])
#         return 0


# 解法三：对解法二进行优化，从两端进行对比，并且删除在wordList中出现过的元素
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: [str]) -> int:
        if endWord not in wordList or beginWord == endWord:
            return 0

        letter = 'abcdefghijklmnopqrstuvwxyz'
        # 没有考虑beginword和endword所以count从2开始
        count, forward, backward = 2, {beginWord}, {endWord}
        while forward:
            # 把短的放前面
            if len(forward) > len(backward):
                forward, backward = backward, forward
            print("forward: ", forward)
            print("backward: ", backward)
            next_word = set()
            for word in forward:
                for i in range(len(word)):
                    for j in range(26):
                        s = word[:i] + letter[j] + word[i+1:]
                        # 如果s出现在后面，说明下一步就是最终结果
                        if s in backward:
                            return count
                        if s in wordList and s not in next_word:
                            next_word.add(s)
                            wordList.remove(s)
            count += 1
            forward = next_word

        return 0


if __name__ == "__main__":
    s = Solution()
    begin = 'hit'
    end = 'cog'
    wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
    count = s.ladderLength(begin, end, wordList)
    print("count: ", count)
